/*
 * Operator.cpp
 *
 *  Created on: 18/06/2011
 *      Author: daniel
 */

#include <iostream>
#include "Operator.h"
#include "stdlib.h"
#include <float.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

/**
 * Retorna un conjunto de movimientos 2-opt.
 * @param: Una solucion.
 * @return: Un vector de movimientos que forman la vecindad.
 */
vector<int*> Operator::twoOptNeighborhood(Solution *s) {

	vector<int*> movs;

	for (int i = 0; i < s->cityNumber - 1; i++) {
		for (int j = i + 2; j < s->cityNumber - 1; j++) {

			double actualCost = s->getCost(i, i + 1) + s->getCost(j, j + 1);
			double improvedCost = s->getCost(i, j) + s->getCost(i + 1, j + 1);

			if (actualCost > improvedCost) {
				int *mov = new int[2];
				mov[0] = i;
				mov[1] = j + 1;
				movs.push_back(mov);
			}
		}
	}
	return movs;
}

/**
 * Retorna el mejor movimiento 2-Opt.
 * @param: Una solucion.
 * @return: int[2] a intercambiar.
 */
int* Operator::twoOptMove(Solution *s) {

	int* best = new int[2];
	double bestCost = DBL_MAX;

	for (int i = 0; i < s->cityNumber - 1; i++) {
		for (int j = i + 2; j < s->cityNumber - 1; j++) {

			double actualCost = s->getCost(i, i + 1) + s->getCost(j, j + 1);
			double improvedCost = s->getCost(i, j) + s->getCost(i + 1, j + 1);

			if (actualCost > improvedCost && (improvedCost < bestCost)) {

				best[0] = i;
				best[1] = j + 1;
				bestCost = improvedCost;
			}
		}
	}
	return best;
}

/*
 * Retorna el mejor movimiento 3-Opt
 * que encuentre.
 */
vector<int*> Operator::threeOptNeighborhood(Solution *s) {

	vector<int*> movs;

	for (int i = 0; i < s->cityNumber - 1; i++) {
		for (int j = i + 2; j < s->cityNumber - 1; j++) {
			for (int k = j + 2; k < s->cityNumber - 1; k++) {

				double actualCost = s->getCost(i, i + 1) + s->getCost(j, j + 1)
						+ s->getCost(k, k + 1);

				double improvedCost = s->getCost(i, j + 1) + s->getCost(k,
						i + 1) + s->getCost(j, k + 1);

				if (actualCost > improvedCost) {

					int *mov1 = new int[2];
					mov1[0] = i + 1;
					mov1[1] = j + 1;

					int *mov2 = new int[2];
					mov2[0] = k;
					mov2[1] = j;

					movs.push_back(mov1);
					movs.push_back(mov2);
				}
			}
		}
	}
	return movs;
}

/**
 * Encuentra una vecindad para una solucion.
 * @param: una solucion y un grado de variacion.
 * @return: Una lista de intercambios que construyen
 * 			la vecindad.
 */
vector<int*> Operator::neighbors(Solution *sact, int paso) {

	int i, j;
	int* mov;

	vector<int*> vecinos;

	for (i = 0; i < sact->cityNumber - paso; i += paso) {
		for (j = i + 1; j < sact->cityNumber; j += paso) {
			mov = new int[2];
			mov[0] = i;
			mov[1] = j;
			vecinos.push_back(mov);
		}
	}
	return vecinos;
}

/**
 * Retorna una solucion nueva a partir de otra.
 * @param: Una solucion.
 * @return: Una solucion.
 */
Solution *Operator::perturbation(Solution *s) {

	//srand(time(NULL));
	Solution *out = s->clone();
	Solution *aux;
	int step;

	if (s->cityNumber > 10)
		step = (random() % (s->cityNumber)) + 3;
	else
		step = 3;

	for (int i = 1; i < out->cityNumber - step - 1; i += step) {

		aux = out;
		out = out->swap(i, i + 1);
		delete aux;
	}

	return out;
}

/**
 *	Perturba una solucion aplicando swaps.
 *	@param: Una solucion.
 *	@return: Una solucion diferente a la que entro.
 */
Solution *Operator::swapPerturbation(Solution *s) {

}

/**
 * Retorna la solucion despues de aplicar el
 * mejor movimiento 3-opt.
 * @param: Una solucion mejorable.
 * @return: Una solucion despues de aplicar
 * 			el mejor movimiento 3-opt.
 */
Solution *Operator::threeOptPerturbation(Solution *s) {

	int *mov1 = new int[2];
	int *mov2 = new int[2];

	Solution *toDelete;
	double bestCost = DBL_MAX;

	for (int i = 0; i < s->cityNumber - 1; i++) {
		for (int j = i + 2; j < s->cityNumber - 1; j++) {
			for (int k = j + 2; k < s->cityNumber - 1; k++) {

				double actualCost = s->getCost(i, i + 1) + s->getCost(j, j + 1)
						+ s->getCost(k, k + 1);

				double improvedCost = s->getCost(i, k) + s->getCost(j, k + 1)
						+ s->getCost(j + 1, i + 1);

				if (actualCost > improvedCost && improvedCost < bestCost) {

					mov1[0] = k;
					mov1[1] = i + 1;

					mov2[0] = k + 1;
					mov2[1] = j + 1;

					bestCost = improvedCost;
				}
			}
		}
	}
	toDelete = s;
	s = s->swap(mov1[0], mov1[1]);
	delete toDelete;

	toDelete = s;
	s = s->swap(mov2[0], mov2[1]);
	delete toDelete;

	return s;
}

/**
 * Retorna la solucion despues de aplicar el
 * mejor movimiento 3-opt.
 * @param: Una solucion mejorable.
 * @return: Una solucion despues de aplicar
 * 			el mejor movimiento 3-opt.
 */
vector<int*> Operator::threeOptMove(Solution *s) {

	vector<int*> movs;

	int *mov1 = new int[2];
	int *mov2 = new int[2];

	Solution *toDelete;
	double bestCost = DBL_MAX;

	for (int i = 0; i < s->cityNumber - 1; i++) {
		for (int j = i + 2; j < s->cityNumber - 1; j++) {
			for (int k = j + 2; k < s->cityNumber - 1; k++) {

				double actualCost = s->getCost(i, i + 1) + s->getCost(j, j + 1)
						+ s->getCost(k, k + 1);

				double improvedCost = s->getCost(i, k) + s->getCost(j, k + 1)
						+ s->getCost(j + 1, i + 1);

				if (actualCost > improvedCost && improvedCost < bestCost) {

					mov1[0] = k;
					mov1[1] = i + 1;

					mov2[0] = k + 1;
					mov2[1] = j + 1;

					bestCost = improvedCost;
				}
			}
		}
	}
	movs.push_back(mov1);
	movs.push_back(mov2);

	return movs;
}

/**
 * Perturba la solucion intercambiando arcos.
 * @param: Una solucion y el grado de perturbacion que
 * 		   se desea.
 */
Solution *Operator::flipArcs(Solution *s, int step, int ini, int fin) {

	Solution *sol = s->clone();

	if (step < 2)
		step = 2;

	if (ini < 0)
		ini = 0;

	if (fin > s->cityNumber)
		fin = s->cityNumber;

	for (int i = ini; i + step < fin - step; i += step) {
		sol = sol->flip(i, i + step);
	}

	return sol;
}

/**
 * Cruza dos soluciones con OX.
 * @param: Dos soluciones.
 * @return: Una solucion cruzada.
 */
Solution *Operator::OX(Solution *a, Solution *b) {

	Solution *hibrid = a->clone();
	vector<int> checked;

	int ini = rand() % (a->cityNumber-1);
	int fin = rand() % (a->cityNumber-1);

	if (fin < ini) {
		int temp = fin;
		fin = ini;
		ini = temp;
	}

	//printf("Nucleo de tamaño:%d, inicio:%d, fin:%d\n", fin-ini, ini, fin);

	// Guarda el nucleo.
	for (int i = ini; i <= fin; ++i)
		checked.push_back(a->tour[i]);

	sort(checked.begin(), checked.end());

	int hi = 0;
	for (int i = 0; i < hibrid->cityNumber && hi < hibrid->cityNumber; ++i) {

		if (hi == ini)
			hi = fin + 1;

		if (!binary_search(checked.begin(), checked.end(), b->tour[i])) {
			hibrid->tour[hi] = b->tour[i];
			hi++;
		}
	}
	hibrid->cost = hibrid->recomputeCost();
	return hibrid;
}
